Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 2
з дисципліни
«Математичні методи дослідження операцій»
Симплекс-метод розв’язку задач
лінійного програмування
Львів – 2008
Мета роботи: набуття навиків розв’язування задач лінійного програмування (ЗЛП) симплекс-методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях у середовищі Еxcel
Порядок роботи:
Заповнити початкову симплекс-таблицю ЗЛП згідно заданого варіанту завдання.
Використовуючи засоби роботи з адресацією в Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям симплекс методу задачі лінійного програмування.
Знайти оптимальний розв’язок і максимальне та мінімальне значення цільової функції.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком:
назва роботи;
мета роботи;
порядок виконання роботи;
короткі теоретичні відомості;
алгоритм побудови розв’язку задачі;
малюнки відповідних таблиць;
одержані результати, їх аналіз і висновки.
Короткі теоретичні відомості про симплекс-метод розв’язування ЗЛП.
Симплекс-метод, який відомий ще як метод послідовного покращення плану, дозволяє послідовно переходити від одного базисного розв’язку до другого, причому так, що значення цільової функції зростають. Оптимальний розв’язок знаходиться при цьому за cкінчену кількість кроків. Алгоритми симплекс-методу дозволяють також відповісти на запитання: чи може бути взагалі розв’язаною конкретна задача лінійного програмування.
Методикою побудови розв’язку, яка найкраще піддається формалізації й алгоритмізації для реалізації на обчислювальній техніці, є метод симплекс-таблиць.
Основою для методу симплекс-таблиць є розширена матриця обмежень. Вона характеризується наявністю одиничної підматриці, причому всі вільні члени мають бути додатні:
Ap = [A1, ..., An, e1, ..., em, A0]. (1)
До такого вигляду можна привести довільну початкову матрицю обмежень застосувавши відомі перетворення.
Алгоритм розв’язування задачі лінійного програмування, наприклад, задачі максимізації методом симплекс-таблиць складатиметься з наступних кроків:
Розрахувати і заповнити початкову таблицю з одиничним базисом у вигляді
C
c1
c3
. . .
cj
. . .
cn
Bx
ai0
A1
A2
A3
. . .
Aj
. . .
An
c1
x1
a10
a11
a12
a13
. . .
a1j
. . .
a1n
c2
x2
a20
a21
a22
a23
. . .
a2j
. . .
a2n
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
ci
xi
ai0
ai1
ai2
ai3
. . .
aij
. . .
ain
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
cm
xm
am0
am1
am2
am3
. . .
amj
. . .
amn
(
a00
a01
a02
a03
. . .
a0j
. . .
a0n
2. За напрямний стовпець Aj вибирають той, для якого
. (2)
3. Напрямний рядок вибирається за умовою:
. (3)
4. Виконується крок симплекс-перетворення з напрямним елементом aij, використовуючи співвідношення:
а) для елементів напрямного рядка
, l = 0, 1, ..., n; (4)
б) для елементів напрямного стовпця
; r = 1, 2, ..., m, причому r ( i; ; (5)
в) для решти елементів матриці
, l ( j, r ( i. (6)
г) для елементів індексного рядка
, , l = 1, 2, ..., n. (7)
Правильність обчислень перевіряється за формулами
, . (8)
Нарешті, в стовпці Bx треба замінити xi на xj, а в стовпці C замінити ci на cj.
5. Якщо, всі елементи симплекс-рядка , l = 1, 2, ..., n, то новий базисний розв’язок , є оптимальним. У випадку, коли ця умова не виконується, переходиться на крок 2 і виконується наступна ітерація.
6. Другий, третій і четвертий кроки повторюються до тих пір, доки одна з ітерацій не завершиться одним із двох результатів:
а) всі , l = 1, 2, ..., n. Умова оптимальності базису останньої табли...
